package com.sheng.leetcode.year2022.month08.day18;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/08/18
 *
 * 1224. 最大相等频率
 *
 * 给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：
 * 从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。
 * 如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。
 *
 * 示例 1：
 * 输入：nums = [2,2,1,1,5,3,3,5]
 * 输出：7
 * 解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。
 *
 * 示例 2：
 * 输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
 * 输出：13
 *
 * 提示：
 *
 * 2 <= nums.length <= 105
 * 1 <= nums[i] <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-equal-frequency
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode1224 {

    @Test
    public void test01() {
        //7
//        int[] nums = {2,2,1,1,5,3,3,5};
        //13
//        int[] nums = {1,1,1,2,2,2,3,3,3,4,4,4,5};
        //8
//        int[] nums = {10,2,8,9,3,8,1,5,2,3,7,6};
        //2
//        int[] nums = {1,2};
        //7
//        int[] nums = {1,1,1,2,2,2,3,3,3};
        //5
//        int[] nums = {1,1,1,2,2,2};
        //13
        int[] nums = {1,2,3,1,2,3,4,4,4,4,1,2,3,5,6};
        System.out.println(new Solution().maxEqualFreq(nums));
    }
}
class Solution {

    Map<Integer, Integer> map;

    public int maxEqualFreq(int[] nums) {
        // 数组前缀，指从0索引处开始的连续子串
        // 满足条件的两种情况：
        // 1.所有数字出现的次数都一样，其中一个出现的次数多一次
        // 2.所有数字出现的次数都一样，其中一个只出现了一次（特殊情况：所有数字都只出现了一次）
        int length = nums.length;
        // map记录nums中所有数字的出现次数
        map = new HashMap<>(16);
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int i = length - 1; i >= 1 ; i--) {
            int num = nums[i];
            //判断前缀是否符合条件
            if (judge()) {
                return i + 1;
            }
            if (map.get(num) == 1) {
                map.remove(num);
            } else {
                map.put(num, map.get(num) - 1);
            }
        }
        return 1;
    }

    public boolean judge() {
        boolean flag = false;
        //key：map中元素的出现次数
        //value：出现次数的统计
        Map<Integer, Integer> hashMap = new HashMap<>(16);
        for (Integer value : map.values()) {
            hashMap.put(value, hashMap.getOrDefault(value, 0) + 1);
        }
        //所有数字都只出现了一次
        if (hashMap.size() == 1 && (hashMap.containsValue(1) || hashMap.containsKey(1))) {
            flag = true;
        } else if (hashMap.size() == 2) {
            //存在{1,1,1,2,2,2,2}和{1,1,1,2,2,2,3}这种情况的，转换后分别为
            //{1,1,1,2,2,2,2}：{3,1},{4,1}
            //{1,1,1,2,2,2,3}：{3,2},{1,1}
            List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(hashMap.entrySet());
            if ((entries.get(0).getValue() == 1 && (entries.get(0).getKey() == 1 || entries.get(0).getKey() - entries.get(1).getKey() == 1))
                    || (entries.get(1).getValue() == 1 && (entries.get(1).getKey() == 1 || entries.get(1).getKey() - entries.get(0).getKey() == 1))) {
                flag = true;
            }
        }
        return flag;
    }
}
